Search for: All records

We introduce a notion of round-robin secure sampling that captures several protocols in the literature, such as the “powers-of-tau” setup protocol for pairing-based polynomial commitments and zk-SNARKs, and certain verifiable mixnets. Due to their round-robin structure, protocols of this class inherently require n sequential broadcast rounds, where n is the number of participants. We describe how to compile them generically into protocols that require only O(\sqrt n) broadcast rounds. Our compiled protocols guarantee output delivery against any dishonest majority. This stands in contrast to prior techniques, which require \Omega(n) sequential broadcasts in most cases (and sometimes many more). Our compiled protocols permit a certain amount of adversarial bias in the output, as all sampling protocols with guaranteed output must, due to Cleve’s impossibility result (STOC’86). We show that in the context of the aforementioned applications, this bias is harmless. 

Many people seem to think that cryptography is all about creating and analyzing cryptographic schemes. This view ignores the centrality of definitions in shaping the character of the field. More than schemes or their analysis, it is definitions that most occupy my thoughts. In this paper, written to accompany an invited talk at Latincrypt 2017, I try to explain my own fascination with definitions. I outline a few of the definitions I’ve recently worked on—garbling schemes, online AE, and onion encryption—and provide some general advice and comments about the definitional enterprise.